package com.ztom.v2;

/**
 * @author ZhangTao
 */
public class Code87LongestIncreasingSubsequence {

    /**
     * 贪心 + 二分
     *
     * @param nums
     * @return
     */
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int[] res = new int[nums.length];
        int index = -1;
        for (int num : nums) {
            // res 第一个元素 || 当前元素 > res 最大的元素 (递增)
            if (index == -1 || num > res[index]) {
                res[++index] = num;
            } else if (num <= res[index]) {
                // 找到大于等于 nums[i] 的位置插入, 形成新的递增序列
                int k = search(res, 0, index, num);
                res[k] = num;
            }
        }
        return index + 1;
    }

    public int search(int[] res, int l, int r, int t) {
        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            if (res[mid] >= t) {
                if (mid == 0 || res[mid - 1] < t) {
                    return mid;
                }
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return -1;
    }

    public int lengthOfLIS1(int[] nums) {
        int[] dp = new int[nums.length];
        // 一个字符
        dp[0] = 1;
        int max = 1;
        for (int i = 1; i < nums.length; i++) {
            int curMax = 0;
            // 以 i 位置结尾
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    curMax = Math.max(curMax, dp[j]);
                }
            }
            // 自己
            dp[i] = curMax + 1;
            max = Math.max(max, dp[i]);
        }
        return max;
    }



    public int lengthOfLIS2(int[] nums) {
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            max = Math.max(max, process(nums, i));
        }
        return max;
    }

    public int process(int[] nums, int index) {
        int curMax = 0;
        // 以 index 位置结尾
        for (int i = 0; i < index; i++) {
            if (nums[i] < nums[index]) {
                curMax = Math.max(curMax, process(nums, i));
            }
        }
        return curMax + 1;
    }
}
